﻿// Eight II HDU - 3567.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*
https://vjudge.net/problem/HDU-3567#author=GPT_zh

八数码问题，又称“九宫格”，源自一个古老的游戏。

在这个游戏中，给定一个 3x3 的棋盘和 8 个方块。方块编号从 1 到 8，每个方块覆盖一个格子。正如你所见，有一个空格可以用 'X' 表示。与空格有公共边的格子中的方块可以移动到空格中。这个操作会导致 'X' 与一个方块交换位置。

我们用符号 'r' 表示将 'X' 与其右侧的方块交换位置，'l' 表示左侧，'u' 表示上方，'d' 表示下方。



棋盘的状态可以用字符串 S 表示，具体规则如下图所示。



问题是通过一系列操作 'r'、'u'、'l'、'd' 将棋盘状态从状态 A 转换到状态 B。你需要找到符合以下条件的结果：
1. 在所有可能解中，它是最短的操作序列之一。
2. 在所有最短操作序列中，它是字典序最小的一个。
输入
第一行是 T (T <= 200)，表示这个问题的测试用例数量。

每个测试用例的输入包括两行，第一行是状态 A，第二行是状态 B。
保证从状态 A 到 B 有可行的解。
输出
对于每个测试用例，期望输出两行。

第一行格式为 "Case x: d"，其中 x 是从一开始计数的案例编号，d 是将 A 转换为 B 所需的最短操作序列长度。
操作序列 S 满足约束条件，应显示在第二行。

2
12X453786
12345678X
564178X23
7568X4123

Case 1: 2
dd
Case 2: 8
urrulldr


*/
int main()
{
    std::cout << "Hello World!\n";
}

 